package com.li.algorithm.leetcode.hot100;

import java.util.Arrays;

public class Test14 {
    public int[][] merge(int[][] intervals) {
        //TODO:根据首节点排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        int[][] result = new int[intervals.length][2];

        //TODO:遍历所有区间，如果当前区间end大于下一区间start，则可以合并
        int i = 0, j = i + 1;
        result[i] = intervals[0];
        int count = 1;
        while (j < intervals.length) {
            while (j < intervals.length) {
                //区间存在重叠，可以合并
                if (result[i][1] >= intervals[j][0]) {
                    //当前end，小于下一区间的end
                    if (result[i][1] < intervals[j][1]) {
                        result[i][1] = intervals[j][1];
                    }
                }
                //不可以合并
                else {
                    i++;
                    result[i] = intervals[j];
                    count++;
                    break;
                }
                j++;
            }
        }
        return Arrays.copyOf(result, count);
    }

    public static void main(String[] args) {
        Test14 test14 = new Test14();
        int[][] result = test14.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        for (int[] res : result) {
            System.out.println(Arrays.toString(res));
        }
    }
}
